Back آلة محدودة الحالات Arabic Краен автомат Bulgarian Konačni automat BS Autòmat finit Catalan Konečný automat Czech Finite-state machine English Finia aŭtomato Esperanto Autómata finito Spanish Lõplik olekumasin Estonian Automata finitu Basque
Ein endlicher Automat (EA, auch Zustandsmaschine, Zustandsautomat; englisch finite state machine, FSM) ist ein Modell eines Verhaltens, bestehend aus Zuständen, Zustandsübergängen und Aktionen. Ein Automat heißt endlich, wenn die Menge der Zustände, die er annehmen kann (später S genannt), endlich ist. Ein endlicher Automat ist ein Spezialfall aus der Menge der Automaten.
Ein Zustand kann Information über die Vergangenheit beinhalten, da das System ihn ja auf dessen bisherigem Weg erreicht hat, d. h., er reflektiert in gewissem Umfang die Änderungen der Eingabe seit dem Systemstart bis zum aktuellen Zeitpunkt.
Ein Zustandsübergang ist ein Übergang aus dem aktuellen Zustand in einen neuen (anderen) Zustand. Zu diesem Übergang kommt es, wenn die angegebenen logischen Bedingungen/„Eingaben“ vorliegen, die erfüllt sein müssen, um den Übergang zu ermöglichen.
Eine Aktion ist die „Ausgabe“ des EA, die in einer bestimmten Situation erfolgt. Es gibt vier Typen von Aktionen:
- Eingangsaktion: Die Aktion wird ausgeführt/ausgegeben beim Eintreten in einen Zustand (egal über welchen Zustandsübergang der Zustand erreicht wurde, falls es mehrere gibt).
- Ausgangsaktion: Die Aktion wird beim Verlassen eines Zustandes generiert (egal über welchen Zustandsübergang der Zustand verlassen wird).
- Eingabeaktion: Die Aktion wird abhängig vom aktuellen Zustand und der Eingabe generiert. Einem Zustand können also mehrere Aktionen zugeordnet sein, die abhängig davon ausgeführt werden, über welchen Zustandsübergang er erreicht/verlassen wird.
- Übergangsaktion: Die Aktion wird abhängig/während eines Zustandsübergangs ausgeführt.
Ein EA kann als Zustandsübergangsdiagramm wie in Abbildung 1 dargestellt werden. Zusätzlich werden mehrere Typen von Übergangstabellen (bzw. Zustandsübergangstabellen) benutzt. Die folgende Tabelle zeigt eine sehr verbreitete Form von Übergangstabellen: Die Kombination aus dem aktuellen Zustand (B) und Eingabe (Y) führt zum nächsten Zustand (C). Die komplette Information über die möglichen Aktionen wird mit Hilfe von Fußnoten angegeben. Eine Definition des EA, die auch die volle Ausgabeinformation beinhaltet, ist mit Zustandstabellen möglich, die für jeden Zustand einzeln definiert werden (siehe auch virtueller EA).
| Momentaner Zustand/ Element des Eingabealphabets |
Element des Eingabealphabets 1 | Element des Eingabealphabets 2 | Element des Eingabealphabets 3 |
|---|---|---|---|
| Zustand A | … | … | … |
| Zustand B | … | Zustand C | … |
| Zustand C | … | … | … |
Die Definition des EA wurde ursprünglich in der Automatentheorie eingeführt und später in der Computertechnik übernommen.
Zustandsmaschinen werden hauptsächlich in der Entwicklung digitaler Schaltungen, Modellierung des Applikationsverhaltens (Steuerungen), generell in der Softwaretechnik sowie Wort- und Spracherkennung benutzt.
Das Testen der Qualität eines Systems umfasst die Überprüfung aller Zustände und Zustandsübergänge, indem alle potenziellen Eingaben in Betracht gezogen werden, die eingegeben werden können. In einigen Fällen wird der endliche Automat unter Verwendung einer Programmiersprache eingerichtet und Zustandsübergangsfunktionen werden ausgeführt. Darüber hinaus kann künstliche Intelligenz verwendet werden, um Daten über Systeme mit Mustererkennung und automatisierten Modellen zu sammeln. Bei einfacheren Problemen können die gleichen Informationen in Tabellen, Matrizen, Abbildungen und Programmablaufplänen angezeigt werden, aber mit endlichen Automaten können größere und kompliziertere Szenarien modelliert werden.[1]
- ↑ TechTarget: finite state machine